package com.atguigu.sort;

import com.sun.org.apache.xerces.internal.xs.ItemPSVI;

import java.util.Arrays;
import java.util.Random;

/**
 * @author 龍
 * 归并排序：利用了归并的思想，该算法采用了经典的分治策略（分：将一些问题分为小的问题，然后递归进行求解，
 * 治：将分的策略得到的答案“修补”在一起，即分而治之）
 * 时间复杂度：nlog n
 * 8千万个数据排序，大约14s
 * sort为9s
 * 快速排序；14s
 * 希尔排序：60
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] array = new int[8000000];
        for (int i = 0; i < array.length; i++) {
            array[i] = new Random().nextInt(800000000);
        }
        System.out.println("排序前的时间：" + System.currentTimeMillis());
        mergeSort(array,0,array.length-1,new int[array.length]);

        System.out.println("排序后的时间：" + System.currentTimeMillis());
        //System.out.println(Arrays.toString(array));

    }

    /**
     * 分+合并
     * @param arr:待排序数组
     * @param left：初始索引
     * @param right：右边索引
     * @param temp：临时数组，做中转的
     */
    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if (left<right){
            //中间索引
            int mid=(left+right)/2;
            //向左递归
            mergeSort(arr,left,mid,temp);
            //向右递归
            mergeSort(arr,mid+1,right,temp);
            //到合并的时候
            merge(arr,left,mid,right,temp);
        }
    }

    /**
     *合并的方法
     * @param arr:待排序数组
     * @param left：初始索引
     * @param mid：中间索引
     * @param right：右边索引
     * @param temp：临时数组，做中转的
     */
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i=left;
        int j=mid+1;
        int t=0;
        //先将左右两边的（有序）数据按照规则填充到temp中，直到左右两边的有序序列处理完毕为止
        while(i<=mid&&j<=right){
            if (arr[i]<=arr[j]){
                temp[t]=arr[i];
                t+=1;
                i+=1;
            }else{
                temp[t]=arr[j];
                t+=1;
                j+=1;
            }
        }
        //一方存在剩余，将有剩余的一边的数据依次全部填充到temp中去
        while (i<=mid){
            temp[t]=arr[i];
            t+=1;
            i+=1;
        }
        while (j<=right){
            temp[t]=arr[j];
            t+=1;
            j+=1;
        }
        //将temp数组中的元素拷贝到arr中去。并不是每次都拷贝所有，第一次tempLeft=0,right=1//2,3//0,3;最后一次才是0，7
        t=0;
        int tempLeft=left;
        while(tempLeft<=right){
            arr[tempLeft]=temp[t];
            t+=1;
            tempLeft+=1;
        }
    }
}
